package org.hhchat.leetcode.dp;

/**
 * Created by HMH on 2017/4/1.
    523 dp

 不断求和取余，如果重复出现了余数，则意味着，中间加了k的倍数。因为n*k+a % k = a。所以如果两次出现a，意味着中间出现了n*k

 public boolean checkSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
    int runningSum = 0;
    for (int i=0;i<nums.length;i++) {
        runningSum += nums[i];
        if (k != 0) runningSum %= k;
        Integer prev = map.get(runningSum);
        if (prev != null) {
            if (i - prev > 1) return true;
        }
        else map.put(runningSum, i);
    }
 return false;

 }


 */
public class code523 {
    public static class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {

            int[] dp = new int[nums.length+2];
            dp[0] = 0;
            for(int i=0;i<nums.length;i++) {
                dp[i+1] = dp[i] + nums[i];
            }

            if(nums.length>2){
                for(int i=0;i<nums.length-1;i++) {
                    for(int j=i+2;j<=nums.length;j++) {
                        if(dp[j]-dp[i]==0 || (k!=0 && (dp[j] - dp[i]) % k == 0)) {
                            return true;
                        }
                    }
                }

            }else if(nums.length==2){
                if(nums[0]+nums[1]==k || ((k!=0)&&(nums[0]+nums[1])%k==0)){
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args){
        System.out.println(new Solution().checkSubarraySum(new int[]{0,1,0},0));
    }
}
